In a communication network, users may establish connections between a source node and a destination node via a flow of data that is transferred through the network over one or more network paths. The data communicated over one or more connections constitutes traffic over the network. A traffic demand in the network between the source node and the destination node is represented by a commodity. A network path for a commodity between the source and destination nodes may be defined by a set of nodes (the source-destination node pair and any intermediate nodes) interconnected by a set of links coupled to the nodes carrying the data flow of the commodity. Each link has a capacity corresponding to the traffic it may carry.
Traffic engineering may be used to decide how to route traffic in a network in order to balance several objectives, including, for example maximizing throughput and efficiency, balancing link utilization across the network, controlling bandwidth allocated to competing flows in a fair manner, minimizing latency and ensuring reliable operations when traffic patterns change or parts of the network fail. Traffic engineering techniques improve network utilization and can, for example, result in routing significantly more traffic through the network than simple network schemes which may route any traffic on the shortest path.
Allocation of shared resources to different users of a network is a fundamental problem in distributed computing and networking. One accepted principle of traffic engineering is that network resources, such as network capacity, belong to all users and should be shared among the users in a fair and non-discriminatory way. Another accepted principle is that a network operator will strive to maximize throughput by allocating bandwidth to maximize the use of network resources. These two principles have conflicting goals, however, the user must be satisfied with the fairness of network allocation, and the network operator must also be satisfied that the network resources are being maximally utilized.
One of the goals of traffic engineering is to achieve a trade-off between fairness and throughput (or efficiency) so that both network users are satisfied with bandwidth allocation and a network operator is satisfied that the network resources are being utilized. Accordingly, systems and methods for balancing these two principles, fairness and throughput, are described herein.